package solution;

import java.util.Stack;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }

        int count = len / 2;
        ListNode p1 = head;
        ListNode p2 = head;
        while (count > 0) {
            p2 = p2.next;
            count--;
        }

        Stack<ListNode> stack = new Stack<>();
        while (p2 != null) {
            stack.push(p2);
            p2 = p2.next;
        }

        while (!stack.isEmpty()) {
            if (p1.val != stack.pop().val) {
                return false;
            }
            p1 = p1.next;
        }

        return true;
    }
}